The encryption or encoding apparatus of a cryptosystem encrypts the plaintext (open text) to be sent in an encrypted form using an encryption key; the encrypted text (ciphertext) is then sent to the receiver of the message, where the decryption or decoding apparatus of the cryptosystem (being at the receiver) decrypts the received ciphertext using a decryption key. It is the common intention of the sender and the receiver that the contents of the plaintext is not to be known by any other party.
As far as the applied encryption keys are concerned, encryption methods can be divided into two major groups:                1. In symmetric-key, or, in other words, private-key cryptosystems the decryption key can be obtained once the encryption key is known, and, vice versa, knowing the decryption key the encryption key can also be obtained. Therefore both keys have to be kept secret, and can be known only by the sender and the receiver of the secret message.        2. In asymmetric-key, or in other words, public-key cryptosystems a public encryption key is applied, the decryption key being known only to the receiver of the secret message. The principle of public key encryption was invented by Diffie and Hellman in 1976 [Diffie, W., Hellman, M. E.: New Directions in Cryptography. IEEE Transactions on Information Theory, vol. IT-22, November 1976, 644-654], before their discovery all cryptosystems applied symmetric keys.        
There is a large number of known encryption algorithms and methods, and their development has been accelerated by the increasing use of the Internet. These trends are present in different countries and regions. In the USA, the so-called Advanced Encryption Standard (AES) [National Institute of Standards and Technology: Advanced Encryption Standard (AES). Federal Information Processing Standards Publication 197. Nov. 26, 2001] is slated to replace the so-called Data Encryption Standard (DES) [Kinnucan, P.: Data Encryption Gurus: Tuchman and Meyer. Cryptologia, No. 2 (4), 1978, 371-381; National Bureau of Standards: Data Encryption Standard (DES). Federal Information Processing Standards Publication (FIPS PUB) 46, National Bureau of Standards, Washington, D.C., 1977]. There are ongoing European and Hungarian projects targeted at developing electronic authentication systems and electronic signatures [The implementation of the European directive on electronic signatures, Landwell Interdisciplinary centre for Law & Information Technology, K. U. Leuven 2001, 1-61], and there is a current Japanese project aiming at the implementation of “electronic government” [Yamada, H.: Current Status of E-Government in Japan and its Future Direction—Electronic Application Services, Science & Technology Trends Quaterly Review, 36 (2010), 19-32].
In the modern history of cryptography there are numerous examples for supposedly very safe cryptosystems that were proven to be breakable as a result of scientific and technological development. A cryptosystem based on simple principles of mathematical logic and probability theory, applying a secret key used only once (one-time pad, OTP system), also called Vernam system [Vernam, G. S.: Secret Signaling System. U.S. Pat. No. 1,310,719, 1919] is the only known cryptosystem that is impossible to break. This is the only cryptosystem with a known mathematical proof of being unbreakable. [Shannon, C. E.: Communication Theory and Secrecy Systems. Bell System Technical Journal, 28 (4), 1949, 656-715]. Although the OTP system is the most reliable form of encryption, in many cases it proves to be impractical. In the OTP system each user has to possess a copy of the key, and the key can only be exchanged over secure communications channels (i.e. face to face). The key can be used only once, and in many applications, the size of the key has to reach the size of the text to be encrypted. Thereby, before encrypting and forwarding a new text, the sender and the receiver have to exchange keys in each case over a secure communications channel. The greatest problem posed by this system is, therefore, precisely that the key can never be reused, and, due to the size of the keys, the key exchange may be extremely cumbersome. The Vernam system is a symmetric-key system.
In the twentieth century, encryption systems developed being more effective than ever before. The strongest boost for this development was provided by the computerisation of encryption methods. The civilian version of the German encryption machine, ENIGMA, was finished after the First World War [Scherbius, A.: Chiffrierapparat. Deutches Reich, Reichspatentamt, Patentschrift Nr. 416219, 1918], the military version of which [Korn, W., Röpke, K.: Elektriesche Chiffriermaschine mit Schreibvorrichtung. Deutsches Reich, Reichspatentamt, Patentschrift Nr. 536556, 1929] was widely used by the German military in the Second World War. The first step in breaking ENIGMA was taken by a French spy, Hans-Thilo Schmidt (being German), who gave photocopies that could be used for reconstructing ENIGMA's wiring to French cryptographers who passed on a copy to the Poles [Paillole, P.: Notre espion chez Hitler, Paris, Editions Robert Laffont, 1985]. Subsequently, based on the results of Polish researchers, a mechanised method was developed by Alan E Turing and his group for breaking this cryptosystem [Gordon, W.: The Hut Six story: Breaking the Enigma codes. Allen Lane & New York, McGraw-Hill, London, 1982].
Similar was the fate of the Japanese mechanised encryption system, PURPLE, which was broken by American researchers [Clark, R. W.: The Man who broke “Purple”: The Life of the World's Greatest Cryptologist. Littlehampton, West Sussex, UK, Littlehampton Book Services, 1977].
The public-key encryption method developed by Ron Rivest, Adi Shamir and Len Adleman in 1977, disclosed in U.S. Pat. No. 4,405,829, has become widely known worldwide under the name RSA (from the initials of the inventors). Today, the RSA algorithm plays a major role in almost all computer and telecommunications systems where the security of digital data has to be ensured. Examples include e-commerce and e-banking systems, ensuring a secure connection between the web server and the clients, the authenticity and confidentiality of e-mail, the use of remote terminals and authentication using electronic credit card systems.
In 1977, Martin Gardner, the world-famous columnist of Scientific American said the following on the possibility of breaking a 125-digit RSA key: [Gardner, M.: Mathematical Games: A New Kind of Chipher That Would Take Millions of Years to Break. Sci. Amer., 237, 1977, 120-124]: “If the present-day best known algorithm and the fastest computers are used, Rivest estimates the necessary resolution time should be approximately 40 quadrillion years!” Less than twenty years passed when in 1996 a 130-digit RSA key was resolved, and nine years later, in 2005, the 640 bit version of RSA was also broken [http://en.wikipedia.org/wiki/RSA_Factoring_Challenge]; with the 768 bit version being also broken in 2009. [Kleinjung, T., Aoki, K., Franke, J., Lenstra, A. K., Thomé, E., Bos, J. W., Gaudry, P., Kruppa, A., Montgomery, P. L, Osvik, D. A., Riele, H. T., Timofeev, A., Zimmermann, P.: Factorization of a 768-bit RSA modulus. In: Rabin, T. (ed.): Advances in Cryptology-CRYPTO 2010, Proc. 30th Annual Cryptology Conference, Santa Barbara, Calif., USA, Aug. 15-19, 2010, 333-350], and one year later RSA 1024 was broken applying a new method based on injecting a fault in the processor of the targeted system. [Pellegrini, A., Bertacco, V., Austin, T.: Fault-Based Attack of RSA Authentication. Univ. Michigan, 2010, http://web.eecs.umich.edu/˜taustin/papers/RSAFault_DATE10. pdf].
A further problem related to cryptosystems is that the security of the widely using public key cryptosystems is based on assumptions that have not been theoretically proven yet. This also applies to the Diffie-Hellman algorithm based on the discrete logarithm problem, [Diffie, W., Hellman, M. E.: New Directions in Cryptography. IEEE Transactions on Information Theory, vol. IT-22, November 1976, 644-654] as well as to the ElGamal algorithm based on the same problem [ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. a.) Advances in cryptology: Proceedings of CRYPTO 84. Lecture Notes in Computer Science. 196. Santa Barbara, Calif., United States: Springer-Verlag. pp. 10-18. b.) IEEE Trans. on Inf. Theory, 31 (1985), 469-472], and to the RSA algorithm that is based on the problem of prime factorization [U.S. Pat. No. 4,405,829]. The experienced drawbacks call for the research and development of cryptosystems based on novel principles. In addition to the fact that the security of these systems is based on unsolved mathematical problems, because of the complexity of the required operations—which in many cases involve high storage space requirements—the systems are impractical. [Buchmann, J. A.: Introduction to Cryptography, 2nd edition. In: Undergraduate Texts in Mathematics, Springer-Verlag, N.Y., Berlin, Heidelberg, 2004]. From a speed aspect, public key systems are also less effective than many symmetric cryptosystems. In practice, therefore these public key systems are usually used in combination with symmetric key systems. Thereby, the usefulness and importance of symmetric key systems is not decreased by the widespread application of public key cryptography.
In 1977, the symmetric key method of Carl Meyer and Walter Tuchman was standardized in the USA as the above mentioned Data Encryption Standard. For an encryption stronger than achievable by DES, the so-called Triple DES, having a triple key length of 168 bits, was later suggested. [National Institute of Standards and Technology: Specifications for the Triple Data Encryption Algorithm (TDEA) Block Cipher. Technology Administration, U. S. Dept. Of Commerce, Special Publication 800-67, 2004, 1-30.], however, a better alternative, applying two keys and being as effective as Triple DES, was suggested by Tuchman [National Institute of Standards and Technology: Federal Information Processing Standards Publication (FIPS PUB) 46-3, National Institute of Standards and Technology, Gaithersburg, Md., 1999]. This latter dual-key system is presently used under the name 3DES. The DES system may be considered as outdated, since the key can be broken in less than a day [Sciengines: Break DES in less than a single day. http://www.sciengines.com/company/news-a-events/74-des-in-1-day.html].
In 2011 it was proven that also 3DES is not secure: applying a side-channel attack (i.e. exploiting certain characteristics of the physical devices implementing the encryption algorithm rather than the characteristics of the algorithm itself), German researchers were able to crack 3DES in only a few hours. [Oswald, D. and Paar, C.: Breaking Mifare DesFire MF3ICD40: Power Analysis and Templates in the Real World. Workshop on Cryptographic Hardware and Embedded Systems-CHES 2011, LNCS 6917, 2011, pp 207-222].
Back in 2001, a new standard encryption algorithm, the Advanced Encryption Standard was introduced in the USA, which has since superseded DES. In 2009, new advances in cryptanalysis were published that pointed out certain weaknesses of the AES algorithms. [Schneier, B.: Another New AES Attack. Schneier on Security, Jul. 30, 2009, http://www.schneier.com/blog/archives/2009/07/another_new_aes.html]. In 2011, an attack (theoretically) capable of key recovery was developed against the 128, 192, and 256 bit AES versions. [A., Khovratovich, D., Rechberger, C.: Biclique Cryptanalysis of the Full AES. Lee, D. H., Wang, X. (eds.), Advances in Cryptology—ASIACRYPT 2011. 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, Dec. 4-8, 2011, LNCS 7013, Springer-Verlag, Heidelberg, 2011, 344-371]. In spite of the above, AES is still considered secure.
Some cryptosystems designed using automata theory are based on Mealy automata or on their generalisation, while others are based on cellular automata. In systems based on Mealy automata the plaintext is fed to a Mealy automaton as an input, and the ciphertext is obtained as the output generated under the effect of this input. Decryption is performed similarly, except that during decryption the ciphertext becomes the input and the plaintext will be the output. In systems based on cellular automata the plaintext is used as a state of the cellular automaton, and the ciphertext is obtained as the state reached after a predetermined number of transitions. Decryption is performed in a similar manner; starting from the ciphertext as a state the initial state is determined which is the decrypted text.
A common problem of these known cryptosystems based on automata theory is that they have serious application difficulties: some of them can be broken [Dawei, D. Wu, K., Huanguo, Z.: Cryptanalysis on a finite automaton public key cryptosystem, Science in China, Series E, Vol 39, No 1 (1996), 27-36 Bao, F.: Cryptoanalysis of partially known cellular automata. In: IEEE Trans. on Computers, 53 (2004), 1493-1497; Meier, W. and Staffelbach, O.: Analysis of pseudo random sequences generated by cellular automata. In: Davies, D. W. (ed.), Proc. Conf. Advances in Cryptology—EUROCRYPT '91, Workshop on the Theory and Application of Cryptographic Techniques, Brighton, UK, Apr. 8-11, 1991, LNCS 547 Springer-Verlag, Berlin, 1991, 186-199], while in case of others the selection of the key automaton poses difficulties [Guan, P.: Cellular automaton public key cryptosystem. Complex Systems, 1 (1987), 51-56].
The connection of different automata through various communication links leads to the notion of “composition of automata” [Gécseg, F.: Products of Automata. EATCS Monogr. Theoret. Comput. Sci. 7, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1986]. A substantial body of literature in this important scientific field has been published by researchers belonging to the automata-theory school centred around Ferenc Gécseg in Szeged, Hungary [Dömösi, P., Nehaniv, C. L.: Algebraic Theory of Automata Networks. An Introduction. SIAM Monographs on Discrete Mathematics and Applications, 11, SIAM, Philadelphia, 2005; Gécseg, F.: Products of Automata. EATCS Monogr. Theoret. Comput. Sci. 7, Springer-Verlag, Berlin, Heidelberg, New York, Tokyo, 1986]. The specific concept of automaton also applied in cryptography, the cellular automaton, can also be regarded a special composition of automata, where the cells functioning as the members of the composition are composed of one and the same type of elementary automata, and the pattern of the communication links and connections between these elementary automata is a simple network. Despite the large number of publications on compositions of automata (authored predominantly by Hungarian researchers), no cryptographic applications of the results have been disclosed so far.
In Hungarian patent with registration number 227 781 a key automaton without output signals (also called automaton without outputs) having initial and final states is applied in an apparatus and method adapted for encryption and decryption of information. According to the document the applied key automaton performs encryption of open data set character by character assigning an encrypted counterpart of variable length to each character, the encryption performed according to the document generating a ciphertext with a length substantially exceeding the length of the plaintext.
A similar solution is disclosed in Hungarian patent with registration number 229 534 (P 08 00148), wherein data encryption and decryption are applied for protecting conditional access broadcasting and datacasting.
The apparatuses and methods according to Hungarian patents Reg. No. 227 781 and 229 534 have the common disadvantage that the ciphertext is significantly longer than the plaintext, with the ciphertext even being multiple times longer than the plaintext.
In view of the known solutions, there is a demand for apparatuses and methods for encrypting and decrypting data that do not cause large-scale size blowup of encrypted data with respect to the corresponding unencrypted data, and preferably comprise a key that is more secure than the keys applied in known encryption/decryption apparatuses and methods.